package com.tgy.查找;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/***
 * @ClassName: BinarySearch
 * @Description: 二分查找
 * @Auther: tanggy3
 * @Date: 14:14 2022/8/31
 * @version : V1.0
 */
public class BinarySearch {
    public static void main(String[] args) {
        int[] arr = {-9, 78, 0, 23, -567, 70, -1, 900, 4561, 1, 0};
        //int[] arr = {1,1,1,1,1,1,1};
        System.out.println(Arrays.toString(sort(arr, 0, arr.length - 1)));
        System.out.println(binarySearch(arr, 0, arr.length - 1, 1));
        ArrayList<Integer> integers = new ArrayList<>();
        System.out.println(binarySearchMulti(arr, 0, arr.length - 1, 1, integers));


    }

    /**
     * 递归版本，需要原始数组是有序的
     *
     * @param arr     原始数组
     * @param left    左边索引
     * @param right   右边索引
     * @param findVal 需要查找的值
     * @return
     */
    public static int binarySearch(int[] arr, int left, int right, int findVal) {
        if (left > right) {
            return -1;
        }
        int mid = (left + right) / 2;
        int temp = arr[mid];
        if (findVal > temp) {
            //中间值小，向右递归 这里mid需要加一不然会出现死循环
            return binarySearch(arr, mid+1, right, findVal);
        } else if (findVal < temp) {
            //中间值大向左递归
            return binarySearch(arr, left, mid-1, findVal);
        } else {
            //相等，返回
            return mid;
        }
    }

    /**
     * @Param
     * @Description: 多个值相同的情况
     * @auther: Tanggy3
     * @date: 20:33 2022/9/19
     * @return:
     */
    public static List<Integer> binarySearchMulti(int[] arr, int left, int right, int findVal, List<Integer> list) {
        if (left > right) {
            return list;
        }
        int mid = (left + right) / 2;
        int temp = arr[mid];
        if (findVal > temp) {
            return binarySearchMulti(arr, mid+1, right, findVal, list);
        } else if (findVal < temp) {
            return binarySearchMulti(arr, left, mid-1, findVal, list);
        } else {
            //向mid 索引值的左边扫描，将所有满足 查找值， 的元素的下标，加入到集合ArrayList
            int temp1 = mid - 1;
            while (true) {
                if (temp1 < 0 || arr[temp1] != findVal) {//退出
                    break;
                }
                //否则，就temp 放入到 resIndexlist
                list.add(temp1);
                temp1 -= 1; //temp左移
            }
            list.add(mid);
            temp1 = mid + 1;
            while (true) {
                if (temp1 > arr.length - 1 || arr[temp1] != findVal) {//退出
                    break;
                }
                //否则，就temp 放入到 resIndexlist
                list.add(temp1);
                temp1 += 1; //temp左移
            }
            return list;
        }
    }


    /**
     * 快速排序
     *
     * @param arr
     * @param left
     * @param right
     * @return
     */
    static int[] sort(int[] arr, int left, int right) {
        if (left < right) {
            int l = left, r = right, x = arr[left];
            while (l < r) {
                while (l < r && arr[r] >= x) r--;//从右向左寻找小于x的数
                if (l < r) arr[l++] = arr[r];

                while (l < r && arr[l] < x) l++;//从右向左寻找小于x的数
                if (l < r) arr[r--] = arr[l];
            }
            arr[l] = x;
            sort(arr, ++l, right);
            sort(arr, left, --r);
        }
        return arr;
    }


}
